package DataStructureAndAlgorithm.Acwing.DP.背包问题DP.零一背包DP.至多背包求解;
/*
状态描述：dp[i][j][k]表示所有从前i个物品中选，总体积不超过j，且总重量不超过k的选法
属性：max
状态表示：
    不选第i个物品的情况：dp[i][j][k] = dp[i - 1][j][k];
    选第i个物品的情况：
        if (j >= v[i] && k >= m[i]){
            dp[i][j][k] = Math.max(dp[i][j][k],dp[i - 1][j - v[i]][k - m[i]] + w[i]);
        }
*/
import java.util.Scanner;
class dp_8{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int V = in.nextInt();
        int M = in.nextInt();
        int[] v = new int[N + 1];
        int[] m = new int[N + 1];
        int[] w = new int[N + 1];
        int[][][] dp = new int[N + 1][V + 1][M + 1];
        for (int i = 1; i <= N; i++){
            v[i] = in.nextInt();
            m[i] = in.nextInt();
            w[i] = in.nextInt();
        }
        for (int i = 1; i <= N; i++){
            for (int j = 1; j <= V; j++){
                for (int k = 1; k <= M; k++){
                    //不选的情况
                    dp[i][j][k] = dp[i - 1][j][k];
                    //相比于一维费用的01背包，这里需要多判断一个条件即可
                    if (j >= v[i] && k >= m[i]){
                        dp[i][j][k] = Math.max(dp[i][j][k],dp[i - 1][j - v[i]][k - m[i]] + w[i]);
                    }
                }
            }
        }
        System.out.print(dp[N][V][M]);
    }
}


//优化后代码
/*
优化方案：
    1.将dp数组从二维降到一维
    2.对于每种物品的信息读入，可以在dp循环中处理
    3.由于每种物品的信息只在当前循环中有用，所以，可以用三个变量代替三个存储物品信息的数组
*/
//class dp_8{
//    public static void main(String[] args){
//        Scanner in = new Scanner(System.in);
//        int N = in.nextInt();
//        int V = in.nextInt();
//        int M = in.nextInt();
//        int v,m,w;
//        int[][] dp = new int[V + 1][M + 1];
//        for (int i = 1; i <= N; i++){
//            v = in.nextInt();
//            m = in.nextInt();
//            w = in.nextInt();
//            for (int j = V; j >= v; j--){
//                for (int k = M; k >= m; k--){
//                    dp[j][k] = Math.max(dp[j][k],dp[j - v][k - m] + w);
//                }
//            }
//        }
//        System.out.print(dp[V][M]);
//    }
//}